package formal.tree.recursion;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 翻转二叉树
 *
 * @author DengYuan2
 * @create 2021-01-11 21:03
 */
public class E_226 {
    public static void main(String[] args) {
//        Integer[] a ={ 4,2,7,1,3,6,9 };
        Integer[] a ={ 1,2,null };
        TreeNode node = TreeNode.generateTree(a);
        node.pre(node);
        System.out.println();
        TreeNode treeNode = invertTree2(node);
        treeNode.pre(treeNode);
//        System.out.println(treeNode);
    }

    /**
     * 我的写法-递归
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left=right;
        root.right=left;
        return root;
    }

    /**
     * 官方-广度优先遍历
     * @param root
     * @return
     */
    public static TreeNode invertTree2(TreeNode root) {
        if (root==null){
            return null;
        }
        Queue<TreeNode> list = new LinkedList<>();
        list.offer(root);
        while (!list.isEmpty()){
//            int size = list.size();
//            for (int i = 0; i < size; i++) {
                TreeNode poll = list.poll();
                TreeNode left = poll.left;
                TreeNode right = poll.right;
                poll.right=left;
                if (left!=null){
                    list.offer(left);
                }
                poll.left=right;
                if (right!=null){
                    list.offer(right);
                }
            }
//        }
        return root;

    }

}
